package cn.lishiyuan.leetcode;

import cn.lishiyuan.algorithm.heap.Heap;

/**
 * LCR 160. 数据流中的中位数 和 295. 数据流的中位数
 *
 * 中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
 *
 * 例如，
 * [2,3,4] 的中位数是 3
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 * 设计一个支持以下两种操作的数据结构：
 *
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 示例 1：
 *
 * 输入：
 * ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
 * [[],[1],[2],[],[3],[]]
 * 输出：[null,null,null,1.50000,null,2.00000]
 * 示例 2：
 *
 * 输入：
 * ["MedianFinder","addNum","findMedian","addNum","findMedian"]
 * [[],[2],[],[3],[]]
 * 输出：[null,null,2.00000,null,2.50000]
 *
 *
 *
 */
public class LeetCode295 {
    // 大顶堆存小元素
    private Heap<Integer> bigHeap = new Heap<>(Heap.HeapType.BIG,32);
    // 小顶堆存大元素
    private Heap<Integer> minHeap = new Heap<>(Heap.HeapType.MIN,32);

    public void addNum(Integer num) {
        // 第一个元素
        if(bigHeap.isEmpty() || num.compareTo(bigHeap.top()) <= 0){
            // 小于大顶堆元素
            ensureCapacity();
            bigHeap.add(num);
        }else {
            ensureCapacity();
            minHeap.add(num);
        }

        // 调整堆,因为没每次只有一个元素的差异，所以只需要调整一个元素
        // 始终维护 bigHeap.size() ≥ minHeap.size() 且差值不超过1
        if(bigHeap.size() > (minHeap.size() + 1) ){
            // 如果大堆大与小堆两个
            ensureCapacity();
            minHeap.add(bigHeap.removeTop());
        }else if(minHeap.size() > bigHeap.size()) {
            // 如果小堆大于大堆
            ensureCapacity();
            bigHeap.add(minHeap.removeTop());
        }
    }

    public double findMedian() {
        if(bigHeap.isEmpty()){
            return Double.NaN;
        }

        int allSize = bigHeap.size() + minHeap.size();

        double result = 0.0;
        if(allSize % 2 == 0){
            // 偶数为堆顶元素之和的平均值
            int sum = bigHeap.top() + minHeap.top();
            result = (double) sum / 2.0;
        }else {
            result = bigHeap.top();
        }

        return result;
    }

    private void ensureCapacity(){
        // 保证容量,双倍扩容
        Heap<Integer> tempBigHeap = bigHeap;
        Heap<Integer> tempMinHeap = minHeap;

        // 更优解是复制底层数组，不过我的heap没有实现复制数组同时设置容量的功能
        if(bigHeap.isFull()){
            bigHeap = new Heap<>(Heap.HeapType.BIG,tempBigHeap.size() * 2);
            while (!tempBigHeap.isEmpty()){
                bigHeap.add(tempBigHeap.removeTop());
            }
        }

        if(minHeap.isFull()){
            minHeap = new Heap<>(Heap.HeapType.MIN,tempMinHeap.size() * 2);
            while (!tempMinHeap.isEmpty()){
                minHeap.add(tempMinHeap.removeTop());
            }
        }

    }
}
